package hash;

/**
 * 基于拉链法实现的哈希表
 * key和value都存储整型
 * @author yuisama
 * @date 2022/01/17 21:03
 **/
public class HashMapByLink {
    // 实际存储的每个节点,冲突时使用单链表链接冲突节点
    private class Node {
        int key;
        int val;
        Node next;
        public Node(int key, int val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    // 实际存储的元素个数
    private int size;
    // 取模数,默认使用数组长度
    private int M;
    // 默认哈希表的长度
    private static final int DEFAULT_CAPACITY = 16;
    // 默认的负载因子
    private static final double LOAD_FACTOR = 0.75;
    // 实际存储Node节点的数组
    private Node[] table;
    public HashMapByLink() {
        this(DEFAULT_CAPACITY);
    }
    public HashMapByLink(int initCap) {
        this.table = new Node[initCap];
        this.M = initCap;
    }

    /**
     * 向哈希表中添加一个键值对
     * @param key
     * @param value
     * @return 若没有重复元素，返回value；若key已经存在，更新为新的value,返回之前的value
     */
    public int put(int key,int value) {
        // 1.先求key的hash值
        int index = hash(key);
        // 2.判断当前哈希表中是否已经存在了这个key，若存在，更新为value，返回旧的value
        // table[index] 就是链表的头节点
        for (Node x = table[index];x != null;x = x.next) {
            if (x.key == key) {
                // 此时哈希表中已经包含了key，更新为新的value，返回旧的value
                int oldVal = x.val;
                x.val = value;
                return oldVal;
            }
        }
        // 3.此时key不存在，新建一个节点头插入相应的链表中(原链表头节点 - table[index])
        Node newNode = new Node(key,value);
        Node head = table[index];
        newNode.next = head;
        // 更新原先头节点的指向为当前节点
        head = newNode;
        table[index] = head;
        size ++;
        // 4.扩容 TODO
        if(size >= LOAD_FACTOR * table.length) {
            resize();
        }
        return value;
    }

    /**
     * 扩容操作，默认将原哈希表长度变为2倍
     */
    private void resize() {
        Node[] newTable = new Node[table.length << 1];
        this.M = newTable.length;
        // 遍历原哈希表
        for (int i = 0; i < table.length; i++) {
            // 取出每个链表的结点，然后映射到新哈希表中
            // 循环进行的条件，此处不能直接使用cur = cur.next
            Node next = null;
            for (Node cur = table[i];cur != null;cur = next) {
                next = cur.next;
                int newIndex = hash(cur.key);
                // 头插入新哈希表中
                cur.next = newTable[newIndex];
                newTable[newIndex] = cur;
            }
        }
        this.table = newTable;
    }

    /**
     * 删除哈希表中指定的键值对
     * @param key
     * @param value
     * @return
     */
    public boolean remove(int key,int value) {
        int index = hash(key);
        // 链表的删除，判断头节点的情况
        if (table[index].key == key) {
            if (table[index].val == value) {
                // 此时头节点就是待删除的节点
                // head = head.next;
                Node head = table[index];
                table[index] = head.next;
                head.next = null;
                size --;
                return true;
            }
        }
        // 头节点不是待删除的节点
        Node prev = table[index];
        while (prev.next != null) {
            if (prev.next.key == key) {
                if (prev.next.val == value) {
                    // prev就是待删除节点的前驱
                    prev.next = prev.next.next;
                    size --;
                    return true;
                }
            }
            prev = prev.next;
        }
        // 此时就不存在这个键值对
        return false;
    }


    // TODO
    public boolean containsKey(int key) {
        return false;
    }
    // TODO
    public boolean containsValue(int value) {
        return false;
    }

    /**
     * 根据key值取得相应的value
     * @param key
     * @return
     */
    public int get(int key) {
        // 求出当前key对应的索引
        int index = hash(key);
        // 遍历index对应的链表，返回key对应的value
        for (Node x = table[index];x != null;x = x.next) {
            if (x.key == key) {
                return x.val;
            }
        }
        // 此时key不存在
        return -1;
    }


    // 最简单的对key取模
    private int hash(int key) {
        // 求绝对值
        return (key & 0x7fffffff) % this.M;
    }
}